__author__ = 'st316'


def partition(data, length, start, end):
    if len(data) == 0 or length < 0 or start < 0 or end >= length:
        return 0

    import random

    index = random.randint(start, end)
    data[index], data[end] = data[end], data[index]

    small = start - 1
    for index in xrange(start, end):
        if data[index] < data[end]:
            small += 1
            if small != index:
                data[index], data[small] = data[small], data[index]
    small += 1
    data[small], data[end] = data[end], data[small]

    return small


def quickSort(data, length, start, end):
    if start == end:
        return
    index = partition(data, length, start, end)
    if index > start:
        quickSort(data, length, start, index - 1)
    if index < end:
        quickSort(data, length, index + 1, end)


if __name__ == '__main__':
    l = [1, 4, 5, 7, 2, -32, 0, 111, 0.7]
    quickSort(l, len(l), 0, len(l) - 1)
    print l